package com.zs.letcode.top_interview_question_medium;

/**
 * 递增的三元子序列
 * 给你一个整数数组nums ，判断这个数组中是否存在长度为 3 的递增子序列。
 * <p>
 * 如果存在这样的三元组下标 (i, j, k)且满足 i < j < k ，使得nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3,4,5]
 * 输出：true
 * 解释：任何 i < j < k 的三元组都满足题意
 * 示例 2：
 * <p>
 * 输入：nums = [5,4,3,2,1]
 * 输出：false
 * 解释：不存在满足题意的三元组
 * 示例 3：
 * <p>
 * 输入：nums = [2,1,5,0,4,6]
 * 输出：true
 * 解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
 *
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 105
 * -231 <= nums[i] <= 231 - 1
 *
 * <p>
 * 进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？
 * <p>
 * 相关标签
 * 贪心
 * 数组
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvvuqg/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/10/8 13:27
 */
public class Chapter6 {

    public static void main(String[] args) {

    }

    private static class Solution {
        /**
         * 只需要使用两个变量即可，一个记录扫描过的最小值，一个记录扫描过的第二小的值。他们的初始值都是Integer.MAX_VALUE
         * <p>
         * 要保证最小值和第二小的值尽可能的小。
         * <p>
         * 如果当前数字比最小值还小，我们就更新最小值
         * 如果当前数字大于最小值并且小于第二小的值，我们就更新第二小的值
         * 如果当前数字大于第二小的值，说明找到了递增的三元子序列，直接返回true。
         * 这里前两条很好理解，我们主要看一下第三条，因为第二小的值默认是Integer.MAX_VALUE，如果当前数字比他大，说明第二小的值已经被赋值了，第二小的值被赋值的条件是最小值也已经被赋值了，因为如果最小值没有被赋值的话，那么最小值优先被赋值。所以这里有个隐含的条件就是，如果第二小的值被赋值了，那么最小的值肯定存在。
         * <p>
         * 作者：数据结构和算法
         * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvvuqg/?discussion=RGAc8M
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         *
         * @param nums
         * @return
         */
        public boolean increasingTriplet(int[] nums) {
            //3个数字，small记录最小的数字
            int small = Integer.MAX_VALUE;
            //mid记录中间的数字
            int mid = Integer.MAX_VALUE;
            for (int num : nums) {
                if (num <= small) {
                    //记录遍历过的最小值
                    small = num;
                } else if (num <= mid) {
                    //记录比small大的最小值，也就是mid的值
                    mid = num;
                } else {
                    //mid如果赋值了，那么之前肯定有个比
                    //mid小的值，这里又有个比mid大的值，
                    //所以他们三个可以构成递增的三元子序列
                    return true;
                }
            }
            return false;
        }
    }
}
